const tree = {
    val: 1,
    left: {
        val: 2,
        left: {
            val: 4,
            left: null,
            right: null
        },
        right: {
            val: 5,
            left: null,
            right: null
        }
    },
    right: {
        val: 3,
        left: {
            val: 6,
            left: null,
            right: null
        },
        right: {
            val: 7,
            left: null,
            right: null
        }
    }
}

// 先序遍历
// 1.访问根节点
// 2. 对根节点的左子树进行先序遍历
// 3. 对根节点的右子树进行先序遍历
// 递归版
const preOrder = (tree) => {
    if (!tree) return
    console.log(tree.val)
    preOrder(tree.left)
    preOrder(tree.right)
}
// preOrder(tree)
// 非递归版
const preOrder1 = (tree) => {
    const stack = [tree]
    while(stack.length > 0) {
        const node = stack.pop()
        console.log(node.val)
        if (node.right) stack.push(node.right)
        if (node.left) stack.push(node.left)
    }
}
// preOrder1(tree)

// 中序遍历
// 1. 对根节点的左子树进行中序遍历
// 2. 访问根节点
// 3. 对根节点的右子树进行中序遍历
const inOrder = (tree) => {
    if (!tree) return
    inOrder(tree.left)
    console.log(tree.val)
    inOrder(tree.right)
}
// console.log(indOrder(tree))
// 非递归版
const inOrder1 = (tree) => {
    const stack = []
    let p = tree
    while(stack.length > 0 || p) {
         while(p) {
             stack.push(p)
             p = p.left
         }
         const n = stack.pop()
         console.log(n.val)
         p = n.right
    }
    
}
inOrder1(tree)

// 后续遍历
// 1. 对根节点的左子树进行后序遍历
// 2. 对根节点的右子树进行后序遍历
// 3. 访问根节点
const postOrder = (tree) => {
    if (!tree) return
    postOrder(tree.left)
    postOrder(tree.right)
    console.log(tree.val)
}
// console.log(postOrder(tree))
// 非递归版
const postOrder1 = (tree) => {
    const stack = [root]
    const outputStack =  []
    while(stack.length > 0) {
        const n = stack.pop()
        outputStack.push(n)
        if (n.left) stack.push(n.left)
        if (n.right) stack.push(n.irght)
    }
    if (outputStack.length) {
        const n = outputStack.pop()
        console.log(n.val)
    }
}
// inOrder1(tree)